package com.yuren.codecrushlearn.Q5200;

/**
 * Created with Intellij IDEA.
 * Description:
 *
 * @author 10204
 * @date 2025-04-28 01:18
 */
public class Q5216 {
    private int[] bitArray;
    private int size;

    // 构造函数，初始化位图的大小
    public Q5216(int size) {
        this.size = size;
        //一个int对应32个bit, size >> 5 相当于 size / 32 使用位计算效率更高
        bitArray = new int[(size >> 5) + 1];
    }

    boolean contains(int value) {
        if (value < 0 || value >= size) {
            return false;
        }
        int arrayIndex = value >> 5;// value / 32
        int bitIndex = value & 31;  // value % 32
        return (bitArray[arrayIndex] & (1 << bitIndex)) != 0;
    }

    // 添加值到位图中
    void add(int value) {
        if (value < 0 || value >= size) {//无法存储
            return;
        }
        int arrayIndex = value >> 5; // value / 32
        int bitIndex = value & 31; // value % 32
        //|按位或运算; <<左移运算; |= 先进行按位或运算，再进行赋值。
        //将 bitArray[arrayIndex] 的第 bitIndex 位置为 1，同时保持其他位不变。
        bitArray[arrayIndex] |= (1 << bitIndex);
    }

    void remove(int value) {
        if (value < 0 || value >= size) {
            return;
        }
        int arrayIndex = value >> 5; // value / 32
        int bitIndex = value & 31; // value % 32
        //~按位取反运算符，将bitArray[arrayIndex] 的第 bitIndex 位清零，而不影响其他位的值。
        bitArray[arrayIndex] &= ~(1 << bitIndex);
    }
}
